package com.kk.datastructure.sort;

import java.util.Arrays;
import java.util.Date;

/**
 * title: 简单选择排序
 * 
 * @author 阿K 
 * 2020年12月7日 下午11:04:18
 */
public class SelectSort {

	public static void main(String[] args) {
//		 int arr[] = {3, 9, -1, 10, 20};
//		 new SelectSort(arr);
//		 System.out.println(Arrays.toString(arr));

		// 测试一下冒泡排序的速度O(n^2), 给80000个数据，测试
		// 创建要给80000个的随机的数组
		int[] arr = new int[80000];
		for (int i = 0; i < 80000; i++) {
			arr[i] = (int) (Math.random() * 8000000); // 生成一个[0, 8000000) 数
		}
		new SelectSort(arr);

	}

	// 策略
	public SelectSort(int[] arr) {
		long time = new Date().getTime();
		selectSort(arr);
		long time2 = new Date().getTime();
		System.out.println("简单选择排序，使用了：" + (time2 - time) + "毫秒");
	}

	// 简单选择排序 Api
	// 选择排序时间复杂度是 O(n^2)
	private static void selectSort(int[] arr) {
		for (int i = 0; i < arr.length - 1; i++) {
			// 每大轮的第一个，假定为最小和后面比较
			int minIndex = i;
			int min = arr[i];
			for (int j = i + 1; j < arr.length; j++) {
				if (min > arr[j]) {// 说明假定的最小不是最小
					minIndex = j;// 重置游标
					min = arr[j];// 重置值
				}
			}
			// 假定的情况（arr[i]，每轮第一个）为最小，不成立
			if (minIndex != i) {
				// 交换
				arr[minIndex] = arr[i];
				arr[i] = min;
			}
		}
	}
}
